/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
#define null NULL
#define sn struct Node
struct Node* copyRandomList(struct Node* head) 
{
	if(head == null)
	{
		return null;
	}
	sn *pr = head;
	while(pr)
	{
		sn * newnode=(sn*)malloc(sizeof(sn));
		newnode->next = newnode->random = null;
		newnode->val = pr->val;
		//每个next节点
		newnode->next=pr->next;
		pr->next=newnode;
		pr = newnode->next;
	}
	//处理random部分
	pr=head;
	while(pr)
	{
		if(pr->random!=null)
		{
			pr->next->random=pr->random->next;
		}
		pr=pr->next->next;
	}
	pr = head;
	//存到到新节点
	sn* nhead = head->next;
	sn* newpr = nhead;
	while(pr&&pr->next->next)
	{
		pr->next=newpr->next;
		pr=pr->next;
		newpr->next=pr->next;
		newpr=newpr->next;
	}
	return nhead;
}
